package vip.zhenzicheng.algorithm.sort;

import vip.zhenzicheng.algorithm.util.ArrayUtils;

import java.util.Arrays;

/**
 * 计数排序
 *
 * @author zhenzicheng
 * @date 2022-06-09 18:36
 */
public class CountingSort {

  public static void main(String[] args) {
    int[] randomArray = ArrayUtils.getRandomArray(30, 50);
    countingSort(randomArray);
    ArrayUtils.printArray(randomArray);
  }

  public static void countingSort(int[] arr) {
    if (arr == null || arr.length < 2) {
      return;
    }
    int min = arr[0], max = arr[0];

    for (int i = 1; i < arr.length; i++) { // 寻找数组中的最大值或最小值
      max = Math.max(arr[i], max);
      min = Math.min(arr[i], min);
    }

    int[] countArr = new int[max - min + 1]; // 计数数组容量
    Arrays.fill(countArr, 0); // 将数组全部填充0
    int countIndex; // 表示在计数数组中的下标
    for (int i = 0; i < arr.length; i++) {
      countIndex = arr[i] - min; // 为了使原来数组中的值能重新落在新数组中的值，相当于每一个数都减去一个最小值就会从[min,max] -> [0, max - min + 1] 中
      countArr[countIndex]++; // 将计数数组中对应位置的元素自增，代表存了一个值为下标的元素
    }

    for (int i = 0, index = 0; i < arr.length; ) {
      if (countArr[index] == 0) {
        index++;
      } else {
        arr[i] = index + min;
        countArr[index]--;
        i++; // 只有真正写入了arr后才移动下标
      }
    }
  }
}
